Union Find [백준]1647 도시 분할 계획(자바) 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리... 최소 스패닝 트리도시 분할 계획알고리즘kruskalUnion FindJava백준자바16471647 백준 1717 집합의 표현 문제 설명 입력이 0 1 2라고 주어지면 1이 포함된 집합과 2가 포함된 집합 합치기 입력이 1 2 3라고 주어지면 2, 3이 같은 집합이면 YES 아니라면 NO 출력 문제 풀이 집합에 포함이 된다? → 같은 부모로 묶여있다. → Union-find 골드 문제에 정답 비율도 낮아서 단순히 union-find로 풀면 시간초과나 놓친 반례가 있을 것이라 생각했는데 그냥 맞았다...ㅎㅎ 소스 코드... Union FindalgorithmUnion Find 백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS [알고리즘] Disjoint Set & Union Find make_set(x) : 초기화 연산, x 스스로만이 집합의 원소이고, 스스로가 집합의 구분자이게 설정한다. union(x, y) : 병합 연산, x가 속한 집합과 y가 속한 집합을 합친다. find(x) : 찾기 연산, x가 속한 집합의 구분자를 반환한다. make_set(x) : size만큼의 array를 할당한 후, array[i] = i로 초기화 하여, 스스로가 집합의 대표번호로 설정... Union FindtreeJavadisjoint setalgorithmCSarrayCS 백준 10775번: 공항 기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다. 그런데 매번 입력받을 때마다 g(i)번부터 1번까지 자리가 있나 탐색을 할 수는 없는 노릇이다. 10만 * 10만이라 시간초과임. 유니온 파인드 자료구조를 통해... Union FindDisjointSetpscppDisjointSet 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet 우주신과의 교감_1774번 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다. 우주신들과의 교감은 우주신... Union Find그래프 이론최소 스패닝 트리Union Find 백준 4195 친구 네트워크 문제 출처 : 이름 2개가 한쌍인 input m개가 주어졌을때 그래프에서 가장 많이 이어져 있는 노드 수 를 출력하는 문제이다. m이 100000이기 때문에 Union Find 알고리즘이 들어가야 한다. input이 string 형으로 주어지기 때문에 map을 사용해 이미 있다면 추가시키지 않고 없다면 노드수를 한개 증가시키고 map에 넣어둔다. 그 다음 find로 2개의 노드의 조상을 찾은... Union FindUnion Find 백준 1717번 집합의 표현 출처 : 저는 이 문제를 파이썬의 딕셔너리 자료형을 이용해서 풀었습니다. info_dic을 통해서 각 숫자가 들어가 있는 집합의 index를 저장 set_dic을 통해서 각 set_dic[index]의 집합을 리스트로 저장 주어진 연산에 따라서 조건문을 통해서 구현 조건은 순서대로 다음과 같다. a, b 가 둘다 정해진 집합이 없을 때 a는 정해진 집합이 없고 b는 정해진 집합이 있을 때 b... 백준코테Union Find알고리즘Union Find 백준 1043 거짓말 이 문제는 지민이가 과장된 이야기를 할 수 있는 파티의 갯수를 구하는 문제이다. 이 때 지민이의 이야기의 진실을 알고 있는 사람이 주어지고 각 파티에 어떤 사람들이 오는지가 번호로 주어진다. 이 문제를 풀기 위해서는 결국 진실을 알고 있는 사람이 속한 파티들을 제외한 파티의 갯수가 답이 되게 된다. 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 과장... Union Find백준분리집합Union Find union-find 알고리즘(합집합 찾기) : 서로소 집합을 구하는 알고리즘 서로소 집합 구조를 표현할 때는 트리 자료구조를 이용한다. 트리는 계층을 갖고 있기 때문에 노드들간의 부모-자식 관계가 있다고 가정한다. ex) 크루스칼 알고리즘 사이클 판별 : x가 속한 집합의 대표값(루트 노드 값)을 반환한다. x가 어떤 집합에 속해 있는지 찾는 연산 [find 알고리즘] 부모노드 테이블을 parent[x]와 x를 똑같이 초기화해놓았기 ... 경로압축Union FindUnion Find [백준] 여행 가자(1976) 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라... Union Find백준Javabackjoon자바알고리즘Java "네트워크" 문제 풀이 이 문제는 프로그래머스에는 DFS, BFS 문제로 분류가 되어있다. 하지만 나는 이 문제를 읽자마자 Union-Find가 떠올랐고 실제로 많은 사람들이 이를 활용하여 문제를 해결했다. 앞으로는 최대한 하루에 한 문제씩 풀어서 풀이를 포스팅할 것이다. 이 문제는 유니온-파인드로 풀었다. 나는 이 알고리즘을 통해 문제를 풀 때 관련 함수들부터 생성한다. 참고로 이 문제에서 사용하는 p array... Union FindJavaScript유니온 파인드알고리즘자바스크립트프로그래머스JavaScript 명예 STL - union-find 자료구조 찾기(find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환 이런 표현을 사용할 때, 두 원소가 같은 트리에 속해있는지 확인하는 방법(즉 find 연산을 구현하는 방법)은 원소가 속해있는 트리의 루트가 같은지를 비교하는 것입니다. 트리와 루트는 항상 1:1 대응되므로(루트가 2개 이상 있는 트리는 존재하지 않으니까) 루트가 같다면 두 원소가 같은 트리에 있음을 자명하게 알... Union Find자료구조Union Find
[백준]1647 도시 분할 계획(자바) 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리... 최소 스패닝 트리도시 분할 계획알고리즘kruskalUnion FindJava백준자바16471647 백준 1717 집합의 표현 문제 설명 입력이 0 1 2라고 주어지면 1이 포함된 집합과 2가 포함된 집합 합치기 입력이 1 2 3라고 주어지면 2, 3이 같은 집합이면 YES 아니라면 NO 출력 문제 풀이 집합에 포함이 된다? → 같은 부모로 묶여있다. → Union-find 골드 문제에 정답 비율도 낮아서 단순히 union-find로 풀면 시간초과나 놓친 반례가 있을 것이라 생각했는데 그냥 맞았다...ㅎㅎ 소스 코드... Union FindalgorithmUnion Find 백준 2162번: 선분 그룹 선분이 교차하면 Union. 유니온 파인드 자료구조에서 p[root]에는 원소의 개수(음수로) 저장. 여기서 둘 다 자세하게 설명했으니 따로 적진 않겠다. 알아야 하는 개념이 좀 많다. 실전에서 이런거 문제로 나오면 시간없어서 못풀듯..... Union FindDisjointSetgeometrycpppsDisjointSet 백준 3197번: 백조의 호수 문명 문제랑 완전 똑같다. 문명이 퍼지는 대신 물이 퍼진다. 퍼질때마다 상하좌우 확인해서 물 있으면 Union, 연도 바뀌면 find. 사실 year가 아니라 day긴 함 ㅋㅋ; 맨 처음에 물이랑 백조 싹다 큐에 넣으면서 상하좌우에 물이나 백조 있으면 Union 해준다. 이거 정답률이 19퍼인데 다들 bfs dfs만 들이박다 시간초과가 나온 듯 하다.... Union FindpsBFScppDisjointSetBFS [알고리즘] Disjoint Set & Union Find make_set(x) : 초기화 연산, x 스스로만이 집합의 원소이고, 스스로가 집합의 구분자이게 설정한다. union(x, y) : 병합 연산, x가 속한 집합과 y가 속한 집합을 합친다. find(x) : 찾기 연산, x가 속한 집합의 구분자를 반환한다. make_set(x) : size만큼의 array를 할당한 후, array[i] = i로 초기화 하여, 스스로가 집합의 대표번호로 설정... Union FindtreeJavadisjoint setalgorithmCSarrayCS 백준 10775번: 공항 기본적인 아이디어는 Greedy하게 남은 게이트 중 가장 번호가 큰 게이트에 도킹시키면 된다. 4를 입력받은 경우 4번 게이트가 남아있으면 4번, 없으면 3번, 3번도 없으면 2번.. 이런식으로 도킹하면 최대한 많이 도킹할 수 있다. 그런데 매번 입력받을 때마다 g(i)번부터 1번까지 자리가 있나 탐색을 할 수는 없는 노릇이다. 10만 * 10만이라 시간초과임. 유니온 파인드 자료구조를 통해... Union FindDisjointSetpscppDisjointSet 백준 17398번: 통신망 분할 완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다. 맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다. 비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.... Union FindDisjointSetpscppDisjointSet 우주신과의 교감_1774번 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다. 우주신들과의 교감은 우주신... Union Find그래프 이론최소 스패닝 트리Union Find 백준 4195 친구 네트워크 문제 출처 : 이름 2개가 한쌍인 input m개가 주어졌을때 그래프에서 가장 많이 이어져 있는 노드 수 를 출력하는 문제이다. m이 100000이기 때문에 Union Find 알고리즘이 들어가야 한다. input이 string 형으로 주어지기 때문에 map을 사용해 이미 있다면 추가시키지 않고 없다면 노드수를 한개 증가시키고 map에 넣어둔다. 그 다음 find로 2개의 노드의 조상을 찾은... Union FindUnion Find 백준 1717번 집합의 표현 출처 : 저는 이 문제를 파이썬의 딕셔너리 자료형을 이용해서 풀었습니다. info_dic을 통해서 각 숫자가 들어가 있는 집합의 index를 저장 set_dic을 통해서 각 set_dic[index]의 집합을 리스트로 저장 주어진 연산에 따라서 조건문을 통해서 구현 조건은 순서대로 다음과 같다. a, b 가 둘다 정해진 집합이 없을 때 a는 정해진 집합이 없고 b는 정해진 집합이 있을 때 b... 백준코테Union Find알고리즘Union Find 백준 1043 거짓말 이 문제는 지민이가 과장된 이야기를 할 수 있는 파티의 갯수를 구하는 문제이다. 이 때 지민이의 이야기의 진실을 알고 있는 사람이 주어지고 각 파티에 어떤 사람들이 오는지가 번호로 주어진다. 이 문제를 풀기 위해서는 결국 진실을 알고 있는 사람이 속한 파티들을 제외한 파티의 갯수가 답이 되게 된다. 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 과장... Union Find백준분리집합Union Find union-find 알고리즘(합집합 찾기) : 서로소 집합을 구하는 알고리즘 서로소 집합 구조를 표현할 때는 트리 자료구조를 이용한다. 트리는 계층을 갖고 있기 때문에 노드들간의 부모-자식 관계가 있다고 가정한다. ex) 크루스칼 알고리즘 사이클 판별 : x가 속한 집합의 대표값(루트 노드 값)을 반환한다. x가 어떤 집합에 속해 있는지 찾는 연산 [find 알고리즘] 부모노드 테이블을 parent[x]와 x를 똑같이 초기화해놓았기 ... 경로압축Union FindUnion Find [백준] 여행 가자(1976) 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라... Union Find백준Javabackjoon자바알고리즘Java "네트워크" 문제 풀이 이 문제는 프로그래머스에는 DFS, BFS 문제로 분류가 되어있다. 하지만 나는 이 문제를 읽자마자 Union-Find가 떠올랐고 실제로 많은 사람들이 이를 활용하여 문제를 해결했다. 앞으로는 최대한 하루에 한 문제씩 풀어서 풀이를 포스팅할 것이다. 이 문제는 유니온-파인드로 풀었다. 나는 이 알고리즘을 통해 문제를 풀 때 관련 함수들부터 생성한다. 참고로 이 문제에서 사용하는 p array... Union FindJavaScript유니온 파인드알고리즘자바스크립트프로그래머스JavaScript 명예 STL - union-find 자료구조 찾기(find) 연산 : 어떤 원소 a가 주어질 때 이 원소가 속한 집합을 반환 이런 표현을 사용할 때, 두 원소가 같은 트리에 속해있는지 확인하는 방법(즉 find 연산을 구현하는 방법)은 원소가 속해있는 트리의 루트가 같은지를 비교하는 것입니다. 트리와 루트는 항상 1:1 대응되므로(루트가 2개 이상 있는 트리는 존재하지 않으니까) 루트가 같다면 두 원소가 같은 트리에 있음을 자명하게 알... Union Find자료구조Union Find